// 基础思想：使用一个额外数组counts，其中counts[i]表示原数组arr中值等于i的元素个数，然后根据数组counts来将arr中元素排到正确的位置
// 步骤： 1. 找出待排序序列中最大值元素arr_max和最小值元素arr_min，2. 定义大小为arr_max - arr_min + 1的数组 3. 遍历数组arr，
// 统计值为num的元素出现的次数，将其次数存入counts数组的num - arr_min项

// 时间复杂度：O(n+k),k代表待排序序列的值域
// 空间复杂度：O(k)，k代表待排序序列的值域，由于用于计数的数组counts的长度取决于待排序数组中数据的范围，所以计数排序算法对于数据范围很大的数组，需要大量的内存
// 计数排序适用情况：一般用于整数排序，不适用按字母顺序，人名顺序结构
// 排序稳定性：稳定排序算法

function countingSort(arr) {
    // 1. 计算序列中最大值元素和最小值元素
    let arr_min = Math.min(...arr)
    let arr_max = Math.max(...arr)

    // 2. 定义计数对象counts
    let size = arr_max - arr_min + 1
    let counts = new Array(size).fill(0)

    // 3. 统计num出现的次数
    for (let i = 0; i < size; i++) {
        let num = arr[i]
        counts[num - arr_min] += 1
    }

    // 4. 计算元素排名
    for (let i = 1; i < size; i++) {
        counts[i] += counts[i - 1]
    }

    // 5. 反向填充目标数组
    let res = new Array(arr.length).fill(0)
    for (let i = arr.length - 1; i >= 0; i--) {
        res[counts[arr[i] - arr_min] - 1] = arr[i]
        counts[arr[i] - arr_min] -= 1
    }
    return res
}

let arr = [2, 7, 26, 25, 7, 19, 17, 1, 90, 3, 36]
console.log(countingSort(arr))
